package com.hanlin.day03;

import java.util.*;

/**
 * @Author:hl.yuan
 * @Date:2024/6/16 15:32
 * @Description: 位运算
 **/
public class ArrayKM {

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 1, 3, 3, 4, 4, 5, 5, 5};
        System.out.println(cale(arr, 2, 3));
        System.out.println(caleMap(arr, 2, 3));
        System.out.println("***********************对数器测试***********************");
        int forNum = 10000;
        int numRange = 100;
        for (int i = 0; i < forNum; i++) {
            // 多少个数据
            int numberNum = getRandom(6);
            int k = getRandom(5);
            int m = getRandom(5);
            //  防止K比M大
            while (k >= m) {
                m++;
            }
            int[] array = createArray(numRange, numberNum, k, m);
            int cale = cale(array, k, m);
            int caleMap = caleMap(array, k, m);
            if (caleMap != cale) {
                Alternator.printArray(array);
                System.out.println("错误了");
            }
        }
        System.out.println("***********************对数器测试***********************");
    }

    /**
     * 使用hashMap实现=》空间复杂度不是O(1)，因为多了一个hashMap的结构
     * 题目：在一个数组中，一个数据出现了K次，其他数都出现了M次，请找到这个数据。
     * 要求：K<M 时间复杂度为O(N) 空间复杂度为O(1)
     *
     * @param array 数组
     * @param k     出现K的次数
     * @param m     出现M的次数
     * @return
     */
    public static int caleMap(int[] array, int k, int m) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (numMap.containsKey(array[i])) {
                numMap.put(array[i], numMap.get(array[i]) + 1);
            } else {
                numMap.put(array[i], 1);
            }
        }
        for (Integer key : numMap.keySet()) {
            if (numMap.get(key) == k) {
                return key;
            }
        }
        return -1;
    }


    /**
     * 题目：在一个数组中，一个数据出现了K次，其他数都出现了M次，请找到这个数据。
     * 要求：K<M 时间复杂度为O(N) 空间复杂度为O(1)
     *
     * @param array 数组
     * @param k     出现K的次数
     * @param m     出现M的次数
     * @return
     */
    public static int cale(int[] array, int k, int m) {
        // 计算数据出现的次数，需要把数据转换成二进制
        int[] temp = new int[32];
        for (int i = 0; i < array.length; i++) {
            // 迭代temp出现的次数
            for (int j = 0; j < temp.length; j++) {
                // 检查array[i] 出现的次数
                temp[j] += (array[i] >> j) & 1;
            }
        }
        int res = 0;
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] % m != 0) {
                res += (1 << i);
            }
        }
        return res;
    }


    /**
     * 随机生成一个数组
     *
     * @param numRange  值的范围【-numRange,numRange】
     * @param numberNum 出现多少个数
     * @return
     */
    public static int[] createArray(int numRange, int numberNum, int k, int m) {
        // [1,numRange]
        Integer range = getRandom(numRange);

        // 数字的最大长度
        Integer arrayMax = k + (numberNum - 1) * m;
        int[] array = new int[arrayMax];
        int kValue = getRandom(numRange);
        // 把K的值添加进去
        for (int i = 0; i < k; i++) {
            array[i] = kValue;
        }
        Set<Integer> set = new HashSet<>();
        set.add(kValue); // 防止后面M的值和K的值相同

        for (int i = 1; i < numberNum; i++) {
            int mValue = getRandom(numRange);
            while (set.contains(mValue)) {
                mValue = getRandom(numRange);
            }
            for (int j = 0; j < m; j++) {
                array[k + ((i - 1) * m) + j] = mValue;
            }
            set.add(mValue);
        }
        return array;
    }

    /**
     * 得到一个随机数
     *
     * @param range
     * @return
     */
    public static int getRandom(int range) {
        return (int) (Math.random() * range) + 1;
    }

}
